import java.io.*;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Random;
import java.util.Scanner;
import java.util.Set;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.Vector;
import java.util.ArrayList;
import java.util.Collections;

public class World {
	/*
	 * BellMan ford section starts
	 */
	public final int INF = Integer.MAX_VALUE;
	// this class represents an edge between two nodes
	class Edge {
		int source; // source node
		int destination; // destination node
		int weight; // weight of the edge
		public Edge() {}; // default constructor
		public Edge(int s, int d, int w) { source = s; destination = d; weight = w; }
	}
	/*
	 * This contains the shortest path length among all node pairs.
	 */
	int[][] minHopTable  ;
	/*
	 * This contains the path information between any two nodes in the network.
	 */
	String[][] path;
	/*
	 * Redundant variable. Remove it later
	 */
	int nodes_count;
	/*
	 * List of UID of all the valid nodes.
	 */
	ArrayList<Integer> nodeList;
	public boolean fillMinHopTable_run = true;
	/*
	 * BellMan ford section ends
	 */

	// TO KEEP THE LIST OF NODES  
	Hashtable <Integer,Node> node;
	// TO MAINTAIN TOPOLOGY.
	// EACH ROW CONTAINS THE NEIGHBOR INFORMATION CORRESPONDING TO NODE IN NETWORK
	Hashtable<Integer, Set<Integer>> topo;
	// UID TO VID MAPPING. 
	int [] uid2vid;
	// VID TO UID MAPPING.
	int []vid2uid;
	// TOTAL NODE COUNT.
	int nNodes, nEdges;
	// PATHID TO PATH STRING MAPPING.  
	Hashtable<String, Integer>pathId;
	// save the information if ith (uid) node is connected or not
	boolean [] isNodeIsolated ;
	// FRACTION AND SEED VALUE
	float fracDrop = 0.0f;
	double seed = 0.0;
	static boolean debug = false;
	ArrayList<Integer> randomGenerated;
	static int pathIdCounter = 0 ;
	String pathFile;

	boolean computeStretch = true;
	boolean recordPairWisePaths = true;
	boolean recordRoutingTables = true;

	public World (String topofile, float fracDrop, double seed){

		node = new Hashtable<Integer, Node>();
		topo = new Hashtable<Integer, Set<Integer>>();
		pathId = new Hashtable<String, Integer>();
		randomGenerated = new ArrayList<Integer>();
		pathFile = topofile;
		this.fracDrop = fracDrop;
		this.seed = seed;
		//1. open the topology file.
		Scanner in_topofile = null;
		try{
			in_topofile = new Scanner(new File(topofile));
		}catch(Exception e){
			e.printStackTrace();
			System.exit(0);
		}

		if(fillMinHopTable_run )fillMinHopTable(topofile);

		nEdges = in_topofile.nextInt();
		nNodes = in_topofile.nextInt();
		uid2vid = new int[nNodes];
		vid2uid = new int[nNodes];
		isNodeIsolated = new boolean[nNodes];
		for (int k = 0; k < nNodes; k++){
			isNodeIsolated[k] = true;
		}
		generateVidMapping();
		int n1,n2; n1 = n2 = 0;
		int n1_vid = 0, n2_vid = 0;

		Random generator = new Random();
		generator.setSeed((long) seed);

		while(in_topofile.hasNextInt()){
			if (generator.nextFloat() < fracDrop){
				in_topofile.nextInt();
				in_topofile.nextInt();
				continue;
			}
			n1 = in_topofile.nextInt() - 1 ;  // -1 IS DONE TO MAKE IT COMPATIBLE 
			n2 = in_topofile.nextInt() - 1;	  // WITH 0 TO N-1 TYPE OF CONVENTION
			// INPUT FILE FORMAT WILL REMAIN UNCHANGED
			println("uid2vid lookup for n1: "+n1,debug);
			isNodeIsolated[n1] = false;
			n1_vid = getVid(n1);	    	    
			println("uid2vid lookup for n2: "+n2,debug);
			n2_vid = getVid(n2);	
			isNodeIsolated[n2] = false;
			println("VID Values : " + n1_vid + " " + n2_vid,debug);

			// now insert n1 into n2's list, and n2 in n1's list
			storeTopology(n1_vid, n2_vid);
		}

		// CREATE NODES
		int vid;
		for (vid = 0 ; vid<nNodes; vid++){
			if (isNodeIsolated[vid2uid[vid]] == false){
				Set<Integer> twoHopNeighbors = new HashSet<Integer>();
				Iterator<Integer> it = topo.get(vid).iterator();
				while (it.hasNext()){
					int oneneighbor = it.next();
					twoHopNeighbors.add(oneneighbor);
					Iterator<Integer> it2 = topo.get(oneneighbor).iterator();
					while (it2.hasNext()){
						twoHopNeighbors.add(it2.next());
					}
				}
				twoHopNeighbors.remove(vid);
				Node newnode = new Node(vid2uid[vid], vid, twoHopNeighbors, this);
				node.put(vid,newnode);
			}
		}
	}

	public void storeTopology(int n1_vid, int n2_vid){
		if (!topo.containsKey(n1_vid)){
			topo.put(n1_vid, new HashSet<Integer>());
		}
		if (! topo.containsKey(n2_vid)){
			topo.put(n2_vid, new HashSet<Integer>());
		}
		topo.get(n1_vid).add(n2_vid);
		topo.get(n2_vid).add(n1_vid);   	
	}

	public int getVid(int uid){

		/*		int vid;
		if (uid2vid.get(uid) == null){
			vid = generateVid();
			println("Mapping of "+uid+ " to vid: "+vid, debug);
			uid2vid.put(uid, vid);
			vid2uid.put(vid, uid);
			println("getVid: I am called here!!", debug);
		}else{
			vid = uid2vid.get(uid);
		}  */  	
		return uid2vid[uid];
	}

	public int generateVid(){

		int x;
		Random rand = new Random();
		rand.setSeed(1);
		do{	
			x = (int)( Math.floor ( rand.nextFloat()* nNodes ) );    	
		}while ( randomGenerated.contains(x));

		randomGenerated.add(x);
		return x; 
	}

	public void  generateVidMapping(){
		ArrayList <Integer> vidset = new ArrayList<Integer>();
		for (int i = 0; i<nNodes; i++){
			uid2vid[i] = -1;
			vid2uid[i] = -1;
			vidset.add(i);
		}

		Random rand = new Random();
		rand.setSeed(1);
		int id;
		for (int i = 0; i< nNodes; i++){
			int randid = rand.nextInt();
			randid = (randid > 0)?randid:-randid;
			id = (randid)%vidset.size();
			//println("ID is: "+id,true);
			uid2vid[i] = vidset.get(id);
			vid2uid[vidset.get(id)] = i;
			vidset.remove(id);
		}
	}

	public int getPathId(int vid1, int vid2){

		String pathKey = Integer.toString(vid1)  + " "+ Integer.toString(vid2);

		if (pathId.containsKey(pathKey)){
			return pathId.get(pathKey);
		}else{
			pathIdCounter++;
			pathId.put(pathKey, pathIdCounter);
			return pathIdCounter;
		}
	}

	public void run() {

		// ITERATE OVER ALL THE NODE'S VID FROM NODE HASHTABLE
		// FILL THE PHYSICAL NEIGHBOR INFORMATION IN THE ROUTING TABLE	   	
		constructRoutingTables();
		//printRoutingTable();

		println("Recording the routing tables now!", true);
		if (recordPairWisePaths)
			recordAllPairPaths();
		if (computeStretch)
			measure_stretch();
		if (recordRoutingTables)
			recordRoutingTable_VRR();
	}

	public void recordAllPairPaths(){

		BufferedWriter bw = null;
		int src, dest;
		try {
			bw = new BufferedWriter(new FileWriter(this.pathFile + ".paths.VRR"));
			bw.write("src(uid) dest(uid) pathlen path\n");

			Iterator<Integer> vidset = node.keySet().iterator();	
			while(vidset.hasNext()){
				src = vidset.next();
				Iterator<Integer> vidset1 = node.keySet().iterator();
				while(vidset1.hasNext()){                		
					dest = vidset1.next();
					if (src !=  dest){
						Path path = new Path(); 
						Message msg = new Message();
						msg.srcVid = src;
						msg.destVid = dest;
						msg.pathId = getPathId(src, dest);              		
						msg.payLoad = path;
						msg.ttl = 512;
						routePacket(msg);
						String towrite = vid2uid[src] + " "+ vid2uid[dest] + " " + 
						((Path)msg.payLoad).pathlen + " " + ((Path)msg.payLoad).path + "\n";
						bw.write(towrite);
						println(towrite,false);                		 
					}
				}
			}  
			bw.close();
		}catch(Exception e){
			e.printStackTrace();
		}
	}

	public void recordRoutingTable_VRR(){

		BufferedWriter bw = null;
		int pathlen = 0, src;
		String towrite = "";
		Node tempNode;
		ArrayList<rtEntry> rtTable; 
		try {
			bw = new BufferedWriter(new FileWriter(this.pathFile + ".rt."+"VRR."+this.fracDrop ));
			for (int i = 0; i< nNodes; i++){
				if (isNodeIsolated[i] == false){
					src = uid2vid[i];
					tempNode = node.get(src);
					rtTable = tempNode.RoutingTable;
					towrite = "RoutingTable at Node(UID): " + i + "\n";
					for (int j =0 ; j < rtTable.size(); j++){
						towrite += "["+j+"] "+vid2uid[rtTable.get(j).nextHop] + " " + vid2uid[rtTable.get(j).end1] + " " + vid2uid[rtTable.get(j).end2] + "\n";
					}
					towrite +="\n";
					bw.write(towrite);
					towrite = "";
				}
				else{
					towrite = "RoutingTable at Node(UID): " + i + "\n";
					towrite+="[]\n";
					bw.write(towrite);
					towrite = "";
				}
			}
			bw.close();
		}catch(Exception e){
			e.printStackTrace();
		}
	}

	public void measure_stretch(){

		BufferedWriter bw = null;
		int physical, nhops;
		int src, dest;
		try {
			bw = new BufferedWriter(new FileWriter(this.pathFile + ".stretch.VRR"));
			bw.write("src(uid) dest(uid) logical_distance physical_distance nhops_using_viro stretch\n");

			Iterator<Integer> vidset = node.keySet().iterator();
			while(vidset.hasNext()){
				src = vidset.next();

				Iterator<Integer> vidset1 = node.keySet().iterator();
				while(vidset1.hasNext()){
					dest = vidset1.next();
					if (src!= dest){
						Path path = new Path();
						Message msg = new Message();
						msg.srcVid = src;
						msg.destVid = dest;
						msg.pathId = getPathId(src, dest);
						msg.payLoad = path;
						msg.ttl = 512;
						routePacket(msg);
						if (msg.ttl == 0){
							nhops = -1;
						}else{
							nhops = ((Path)msg.payLoad).pathlen; 
						}
						physical = getPhysicalDist(src, dest);
						println("vids: src = "+src+" dest = "+dest+"\tuids: src = "+vid2uid[src]+" dest = "+vid2uid[dest],debug);
						String towrite =src + " "+ dest + " -1 " + physical + " "+nhops+" "+ (float)nhops/(float)physical+"\n" ;
						bw.write(towrite);
						println(towrite,false);
						Thread.sleep(100);
					}
				}
			}
			bw.close();
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

	/*
	 * TODO: UPDATE THE MESSAGE PAYLOAD WITH EVERY VISIT
	 * CHECK FOR RECURSION OR ITERATION
	 * JAVA PASS BY REFERENCE OR PASS BY VALUE
	 */

	public void routePacket(Message msg){

		int currentnode, nextHop;
		Node tempnode;
		if (msg.ttl == 0){
			return;
		}       	

//		currentnode = msg.srcVid;
//		if (currentnode != msg.destVid){
//		tempnode = node.get(currentnode);
//		nextHop = tempnode.getNextHop(msg);
//		if (nextHop == -1){
//		//DROP THE PACKET.
//		}
//		else{
//		((Path)msg.payLoad).pathlen++;
//		((Path)msg.payLoad).path= ((Path)msg.payLoad).path  + vid2uid.get(currentnode) + " ";   			    			
//		msg.ttl--;
//		msg.srcVid = nextHop;
//		routePacket(msg);
//		}
//		}else{
//		/*
//		* MESSAGE REACHED SUCCESSFULLY
//		* NO NEED TO SEND ACKNOWLEDGEMENT
//		*/
//		}
		currentnode = msg.srcVid;
		while (currentnode != msg.destVid && currentnode != -1){
			msg.ttl--;
			((Path)msg.payLoad).pathlen++;
			((Path)msg.payLoad).path= ((Path)msg.payLoad).path  + vid2uid[currentnode] + " ";   			
			currentnode = node.get(currentnode).getNextHop(msg);
			if (msg.ttl <= 0){
				println("TTL expired!! possible routing loop : "+msg, true);
				break;
			}
		}
		((Path)msg.payLoad).pathlen++;
		((Path)msg.payLoad).path= ((Path)msg.payLoad).path  + vid2uid[currentnode];  

		return; 	
	}

	public void constructRoutingTables(){
		Iterator<Integer> vidset = node.keySet().iterator();
		while(vidset.hasNext()){
			int vid = vidset.next();
			println("Buidling routing table for the node: "+vid, false);
			node.get(vid).buildRoutingTable();  		
		}    	
	}

	public void printRoutingTable(){

		Iterator<Integer> vidset = node.keySet().iterator();
		Node tempnode;
		int nodeVid;
		rtEntry r;
		while (vidset.hasNext()){

			tempnode = node.get(vidset.next());
			nodeVid = tempnode.myvid;
			ArrayList<rtEntry> rt = tempnode.RoutingTable;
			System.out.println("ROUTING TABLE CORRESPONDING TO NODE:" + nodeVid + "\n");
			System.out.println("NEXTHOP\tPATHID\tEND1\tEND2\tTYPE\n");
			System.out.println("---------------------------------\n");
			for (int i =0; i< rt.size(); i++ ){
				r = rt.get(i);
				r.printMe();
			}
			System.out.println("---------------------------------\n");
		}
	}

	public String getPath(int vid1, int vid2){

		int uid1 = vid2uid[vid1];
		int uid2 = vid2uid[vid2];
		String path_nodes = path[uid1][uid2];

		return path_nodes;
	}

	public int getPhysicalDist(int vid1, int vid2){

		int physical;
		if (nodeList.contains((vid2uid[vid1])) && nodeList.contains((vid2uid[vid2]))){
			physical = minHopTable[(vid2uid[vid1])][(vid2uid[vid2])] ;
		}else{
			physical = -1;
		}
		return physical;
	}

	public int getOSPFnextHop(int vid1, int vid2){

		if (isNodeIsolated[vid2uid[vid1]] == true){
			println("Vid2uid does not contain vid1 "+vid1, false);
			return -1;
		}
		if (isNodeIsolated[vid2uid[vid2]] == true){
			println("Vid2uid does not contain vid2 "+vid2, false);
			return -1;
		}	
		int uid1 = vid2uid[vid1];
		int uid2 = vid2uid[vid2];
		String path_nodes = path[uid1][uid2];
		println("Path is: "+path_nodes, false);
		StringTokenizer tok = new StringTokenizer(path_nodes); 
		if (tok.countTokens() > 1){
			tok.nextToken();
			return uid2vid[Integer.parseInt(tok.nextToken())];
		}else if(tok.countTokens() == 1){
			return vid2;		 
		}else {
			return -1;
		}
	}

	/*
	 * TOPOFILE FORMAT 
	 * EDGES ARE NUMBERED FROM 0 TO N-1
	 * FILE CONTAINS ALL THE CONNECTING EDGE INFORMATION
	 */

	// FILLING THE PATH INFORMATION IN THE ARRAY........... 
	public void fillMinHopTable(String topofile){

		/*
		 * EDGES WILL CONTAIN ALL THE EDGES FOR TOPOLOGY
		 */
		Vector<Edge> edges = new Vector<Edge>();
		/*
		 * NODELIST IS LIST OF ALL THE NODES
		 */
		nodeList = new ArrayList<Integer>();

		String[] tok = new String[3];
		String line = new String();
		int maxNodeId = -1, temp;

		/*
		 * DATAINPUT STREAM HANDLE
		 * -G OPTION INDICATE BACKWARD COMPATIBILITY
		 * BELLMANFORD ASSUMES THAT TOPOLOGY FILE SHOULD BE:
		 * <NUMBER OF NODE>
		 * VERETX1 VERTEX2 WEIGHT
		 * VERTEX1 VERTEX3 WEIGHT
		 *
		 * HERE VERTEX STARTS FROM 0....(N-1)
		 */
		try{
			DataInputStream dis = new DataInputStream(new FileInputStream(topofile));
			dis.readLine();
			Random generator = new Random();
			//Date d = new Date();
			//long time = System.currentTimeMillis();
			System.out.println("Seed time value is:"+seed);
			generator.setSeed((long) seed);

			while ((line = dis.readLine()) != null){
				/*
				 * DROPPING PACKETS RANDOMLY
				 */
				if (generator.nextFloat() < fracDrop){
					continue;
				}
				/*
				 * SPLIT LINE ON SPACES
				 */
				tok = line.split(" ");
				/*
				 * ASSUMES WEIGHT TO BE 1
				 */
				edges.add(new Edge(Integer.parseInt(tok[0]) -1, Integer.parseInt(tok[1]) -1, 1));
				edges.add(new Edge(Integer.parseInt(tok[1]) - 1, Integer.parseInt(tok[0]) - 1, 1));

				/*
				 * -1 IS DONE TO START NODES FROM 0....
				 * OTHERWISE PUT DUMMY VALUE AT 0TH CELL ROW
				 * AND START LOOP FROM 1.
				 */

				if (! nodeList.contains(Integer.parseInt(tok[0])-1)){
					nodeList.add(Integer.parseInt(tok[0])-1);
				}
				if (! nodeList.contains(Integer.parseInt(tok[1])-1)){
					nodeList.add(Integer.parseInt(tok[1])-1);
				}
				temp = ((Integer.parseInt(tok[0])-1) > (Integer.parseInt(tok[1])-1))?
						((Integer.parseInt(tok[0])-1)):(Integer.parseInt(tok[1])-1);

						/*
						 * MAXNODEID DENOTES THE MAXIMUM VALUE OF NODEID
						 * INTRODUCED TO TACKLE THE DROP PROBLEM
						 * IF EVERYTHING IS FINE THEN MAXID = <NUMBER OF NODES> - 1
						 */
						if (maxNodeId < temp )
							maxNodeId = temp;
			}
			println("size of arraylist " + nodeList.size(),debug);
			minHopTable = new int[maxNodeId+1][maxNodeId+1];
			path = new String[maxNodeId+1][maxNodeId+1];
			nodes_count = maxNodeId+1;
			Collections.sort(nodeList);
			/*
			 * CALL BELLMANFORD FOR EACH NODE IN NODELIST ....
			 */
			int i = 0;
			for (i = 0; i < nodeList.size(); i++){
				bellmanFord(edges, maxNodeId+1, (Integer)nodeList.get(i));
			}
			/*
			 * PRINT THE MINHOPTABLE FOR EACH NODE...
			 */
			for ( i = 0; i< nodeList.size(); i++){
				for (int j =0 ; j< nodeList.size(); j++)
					println("Distance between " + i + " and " + j + "is " + minHopTable[nodeList.get(i)][nodeList.get(j)] + "\n", debug);
			}
		}
		catch(FileNotFoundException fe){
			System.out.println("error here\n");
			fe.printStackTrace();
		} catch (IOException ie){
			System.out.println();
			ie.printStackTrace();
		}
	}

	public void bellmanFord(Vector<Edge> edges, int nnodes, int source) {
		// the 'distance' array contains the distances from the main source to all other nodes
		int[] distance = new int[nnodes];

		for (int i = 0 ; i < nnodes; i++){
			path[source][i] = new String("");
		}

		//initially set - all distances are initiated to infinity
		Arrays.fill(distance, INF);
		// the distance from the main source to itself is 0
		distance[source] = 0;
		// in the next loop we run the relaxation 'nnodes' times to ensure that
		// we have found new distances for ALL nodes
		for (int i = 0; i < nnodes; ++i)
			// relax every edge in 'edges'
			for (int j = 0; j < edges.size(); ++j) {
				// analyze the current edge (SOURCE == edges.get(j).source, DESTINATION == edges.get(j).destination):
				// if the distance to the SOURCE node is equal to INF then there's no shorter path from our main source to DESTINATION through SOURCE
				if (distance[edges.get(j).source] == INF) continue;
				// newDistance represents the distance from our main source to DESTINATION through SOURCE (i.e. using current edge - 'edges.get(j)')
				int newDistance = distance[edges.get(j).source] + edges.get(j).weight;
				// if the newDistance is less than previous shortest distance from our main source to DESTINATION
				// then record that new shortest distance from the main source to DESTINATION
				if (newDistance < distance[edges.get(j).destination]){
					path[source][edges.get(j).destination] = path[source][edges.get(j).source] +" " + Integer.toString((edges.get(j).source));
					distance[edges.get(j).destination] = newDistance;
				}
			}
		// next loop analyzes the graph for cycles
		for (int i = 0; i < edges.size(); ++i)
			// 'if (distance[edges.get(i).source] != INF)' means:
			// "
			//     if the distance from the main source node to the DESTINATION node is equal to infinity then there's no path between them
			// "
			// 'if (distance[edges.get(i).destination] > distance[edges.get(i).source] + edges.get(i).weight)' says that there's a negative edge \
			// weight cycle in the graph
			if (distance[edges.get(i).source] != INF && distance[edges.get(i).destination] > distance[edges.get(i).source] + edges.get(i).weight){
				System.out.println("Negative edge weight cycles detected!");
				return;
			}
		// this loop outputs the distances from the main source node to all other nodes of the graph
		for (int i = 0; i < distance.length; ++i)
			if (distance[i] == INF){
				println("There's no path between " + source + " and " + i, debug);
				minHopTable[source][i] = distance[i];
			}
			else{
				println("The shortest distance between nodes " + source + " and " + i + " is " + distance[i],debug);
				minHopTable[source][i] = distance[i];
			}
		for (int i = 0; i < nnodes; ++i){
			println("Path from"+ source +" to " + i + "is as this:" + path[source][i],debug);
		}
	}

	public static void println(String string, boolean debug) {
		// TODO Auto-generated method stub
		if (debug == true){
			System.out.println(string);
		}

	}
}
